/**
 * @ClassName KP19_reverseNodesInKGroup
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/10/13 16:12
 */

/**
 *  K 个一组翻转链表
 */
public class KP19_reverseNodesInKGroup {

    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode start = head;
        ListNode end = getKGroupEnd(start, k);
        if (end == null) {
            return head;
        }
        // 翻转的新头结点
        head = reverse(start,end);
        // 上一组的结尾结点
        ListNode preEnd = start;
        while (preEnd.next != null) {
            start = preEnd.next;
            end = getKGroupEnd(start, k);
            if (end == null) {
                return head;
            }
            preEnd.next = reverse(start, end);
            preEnd = start;
        }
        return head;
    }

    /**
     * 返回第K个列表
     */
    public ListNode getKGroupEnd(ListNode cur, int k) {
        /*ListNode end = null;
        while (--k != 0 && cur != null) {
            cur = cur.next;
            end = cur;
        }
        return end;*/

        while (--k != 0 && cur != null) {
            cur = cur.next;
        }
        return cur;
    }

    /*public void reverse(ListNode start,ListNode end) {
        end = end.next;
        ListNode mark = start;
        ListNode pre = null;
        ListNode next = null;
        while (start != end) {
            next = start.next;
            start.next = pre;
            pre = start;
            start = next;
        }
        mark.next = end;
     }*/

    public ListNode reverse(ListNode start,ListNode end) {
        end = end.next;
        ListNode mark = start;
        ListNode pre = null;
        ListNode next = null;
        while (start != end) {
            next = start.next;
            start.next = pre;
            pre = start;
            start = next;
        }
        mark.next = end;
        return pre;
    }
}
